/**
 * класс граф, хранит граф и выполняет над ним некоторые операции
 */
class Graph {
	/**
	 * количество вершин графа
	 */
	private int n;
	/**
	 * матрица R
	 */
	private int[][] R;
	/**
	 * конструктор пустого графа - n несвязанных вершин
	 */
	public Graph (int n) {
		R = new int[n][n];
		this.n = n;
		for (int i = 0; i < n; ++ i)
			for (int j = 0; j < n; ++ j)
				R[i][j] = 0;
	}
	/**
	 * @return количество вершин графа
	 */
	public int count () {
		return n;
	}
	/**
	 * @return количество рёбер графа
	 */
	public int countEdges () {
		int count = 0;
		for (int i = 0; i < n; ++ i)
			for (int j = i + 1; j < n; ++ j)
				count += R[i][j];
		return count;
	}
	/**
	 * добавить несколько рёбер между двумя вершинами
	 * @param int i первая вершина
	 * @param int j вторая вершина
	 * @param int edge_value количество рёбер
	 */
	public void addEdge (int i, int j, int edge_value){
		R[i][j] += edge_value;
		R[j][i] += edge_value;
	}
	/**
	 * провести между двумя вершинами некоторое количество рёбер
	 * @param int i первая вершина
	 * @param int j вторая вершина
	 * @param int edge_value количество рёбер
	 */
	public void setEdge (int i, int j, int edge_value){
		R[i][j] = edge_value;
		R[j][i] = edge_value;
	}
	/**
	 * получить количество рёбер между двумя вершинами
	 * @param int i первая вершина
	 * @param int j вторая вершина
	 * @return количество рёбер
	 */
	public int getEdge (int i, int j) {
		return R[i][j];
	}
	/**
	 * степень вершины
	 * @param int i вершина
	 * @return количество рёбер, выходящих из неё
	 */
	public int degree (int i) {
		int count = 0;
		for (int j = 0; j < n; ++ j)
			count += R[i][j];
		return count;
	}
	/**
	 * поменять местами две вершины
	 * @param int i первая вершина
	 * @param int j вторая вершина
	 */
	public void swap (int i, int j) {
		for (int u = 0; u < n; ++ u){
			int temp = R[i][u];
			R[i][u] = R[j][u];
			R[j][u] = temp;
			temp = R[u][i];
			R[u][i] = R[u][j];
			R[u][j] = temp;
		}
	}
	/**
	 * @return является ли граф полным
	 */
	public boolean isFull () {
		for (int i = 0; i < n; ++ i)
			for (int j = 0; j < n; ++ j)
				if (i != j && getEdge (i, j) == 0)
					return false;
		return true;
	}
	/**
	 * стянуть ребро uv (две вершины объединить в одну)
	 * @param int u первая вершина
	 * @param int v вторая вершина
	 */
	public void couple (int u, int v) {
		for (int i = 0; i < n; ++ i) {
			R[u][i] += R[v][i];
			R[i][u] += R[i][v];
		}
		remove (v);
	}
	/**
	 * удалить вершину
	 * @param int v вершина
	 */
	public void remove (int v) {
		int [][]newR = new int[n - 1][n - 1];
		for (int i = 0; i < n; ++ i)
			for (int j = 0; j < n; ++ j)
				if (i != v && j != v) {
					int newi = (i <= v ? i : i - 1);
					int newj = (j <= v ? j : j - 1);
					newR[newi][newj] = R[i][j];
				}
		R = newR;
		-- n;
	}
	/**
	 * вернуть копию графа
	 */
	public Graph clone () {
		Graph g = new Graph (n);
		for (int i = 0; i < n; ++ i)
			for (int j = 0; j < n; ++ j)
				g.setEdge (i, j, getEdge (i, j));
		return g;
	}
}